local arrayext = require("arrayext")

local Deque = {}
Deque.__cname = "util.Deque"
Deque.__index = Deque

local ClearTypeEnum = {
    Reset = nil,
    FillNil = 1,
    Keep = 2,
}
Deque.ClearTypeEnum = ClearTypeEnum

function Deque.new(capacity)
    local obj = {}
    setmetatable(obj, Deque)
    obj:ctor(capacity)
    return obj
end

function Deque:ctor(capacity)
    self.arr = {}
    self.capacity = capacity or 8
    self.head = 1 ---当前:先加减再操作
    self.tail = 1 ---后一个位置: 先操作再加减
    self.count = 0
end

function Deque:Clear(clearType)
    if self:GetCount() < 1 then return end

    if clearType == ClearTypeEnum.Reset then
        self.arr = {}
    elseif clearType == ClearTypeEnum.FillNil then
        if self.head < self.tail then
            for i=self.head,self.tail-1 do
                self.arr[i] = nil
            end
        else
            for i=self.head,self.capacity do
                self.arr[i] = nil
            end
            for i=1,self.tail-1 do
                self.arr[i] = nil
            end
        end
    end
    self.capacity = 0
    self.head = 1
    self.tail = 1
    self.count = 0
end

function Deque:GetCount()
    return self.count
end

function Deque:_GetMod(index)
    if index > self.capacity then
        index = index - self.capacity
    elseif index < 1 then
        index = index + self.capacity
    end
    return index
end

function Deque:_Expand()
    if self.head > 1 then --尾跟头相接, 把尾跟头的位置调过来
        local j = 1
        for i=self.head,self.capacity do
            arrayext.Swap(self.arr, j, i)
            j = j + 1
        end
        --注意: 交换次数为奇数次, 还要再多交换一次(把最后2个元素调整下)
        local swapCount = self.capacity - self.head + 1
        if 1 == math.fmod(swapCount, 2) then
            arrayext.Swap(self.arr, self.capacity, self.capacity - 1)
        end
    end

    self.head = 1
    self.tail = self.count + 1
    self.capacity = self.capacity * 2
end

function Deque:AddFirst(v)
    self.head = self:_GetMod(self.head - 1)
    self.arr[self.head] = v
    self.count = self.count + 1

    if self.head == self.tail then
        self:_Expand()
    end
end

function Deque:AddLast(v)
    self.arr[self.tail] = v
    self.tail = self:_GetMod(self.tail + 1)
    self.count = self.count + 1

    if self.head == self.tail then
        self:_Expand()
    end
end

function Deque:PeekFirst()
    if self:GetCount() < 1 then return nil end
    return self.arr[self.head]
end

function Deque:PeekLast()
    if self:GetCount() < 1 then return nil end
    local index = self:_GetMod(self.tail - 1)
    return self.arr[index]
end

function Deque:RemoveFirst()
    if self:GetCount() < 1 then return nil end
    local ret = self.arr[self.head]
    self.arr[self.head] = nil

    self.head = self:_GetMod(self.head + 1)
    self.count = self.count - 1
    return ret
end

function Deque:RemoveLast()
    if self:GetCount() < 1 then return nil end
    local removeIndex = self:_GetMod(self.tail - 1)

    local ret = self.arr[removeIndex]
    self.arr[removeIndex] = nil

    self.tail = removeIndex
    self.count = self.count - 1
    return ret
end

function Deque:__tostring()
    if self:GetCount() < 1 then return "" end

    local strTb = {}
    if self.head < self.tail then
        for i=self.head,self.tail-1 do
            table.insert(strTb, tostring(self.arr[i]))
        end
    else
        for i=self.head,self.capacity do
            table.insert(strTb, tostring(self.arr[i]))
        end
        for i=1,self.tail-1 do
            table.insert(strTb, tostring(self.arr[i]))
        end
    end

    return table.concat(strTb, ",")
end

function Deque:GetIterator()
    --todo: 不能RemoveLast
    if nil == self.iterator then
        self.iterator = function(tb, key)
            return self:RemoveLast()
        end
    end
    return self.iterator
end

return Deque
